/*
Date:20210509 10:37AM
key:sum为一天就能带走的运货量，min为最小单个带法。
    从左往右，当weight能满足，则右皆满足，不能则左皆不能，因此可二分


*/
class Solution {
public:
    bool check(vector<int>& weights,int&D,int &lim)
    {
        int day=0;
        int tmp=0;
        for(int& g:weights)
        {
            //单日超过lim
            if(g>lim){return false;}
            //某日超过lim，日子加1.
            if(g+tmp>lim){tmp=0;day++;}
            tmp+=g;
        }
        //合适lim时应该为day+1=D,因此现在是day<D。
        return day<D;
    }
    int shipWithinDays(vector<int>& weights, int D) 
    {
        int l=*min_element(weights.begin(),weights.end());
        int r=accumulate(weights.begin(),weights.end(),0);
        while(l<r)
        {
            int mid=(l+r)>>1;
            //cout<<mid<<endl;
            //为1则day太多,lim小了
            if(!check(weights,D,mid))
            {
                l=mid+1;
            }
            else{r=mid;}
        }
        return r;
    }
};